package algorithm.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 选择排序
 * 优化
 *   从前往后+从后往前 实现
 *   一下取出两个选出最小的在和基定值对比 相当于一下跳两个。 待完成。 i+=2 的往前跳。 没感觉这个有多牛逼。
 *
 *   手动对O进行分析
 *
 *   什么是不稳定？
 *   就是排序完了两个相等的数的位置会变化。 a[a0,b0] 排序完了可能是 a[b0,a0]
 *
 *   工程上如何验证算法的准确性？
 *     大数法则
 *     对数器的概念
 */
public class SelectSort {
    public static void main(String[] args) {
//        System.out.println("选择排序");

        int [] list = SelectSort.ay(); // 不计入算法时间 - 空间复杂度 O(1) 空间复杂度是算法用的额外空间。
        int r = 0; // 临时变量 算法需要用的 算入空间复杂度。 O(1)

        int [] cy = new int[list.length];
        System.arraycopy(list,0,cy,0, list.length);

        System.out.println("start自己排序");
        long start = System.currentTimeMillis();
        for(int i = 0; i < list.length - r; i++){ // [int i = 0; O(1)]  [list.length  rO(n-1)] [i++ O(n)]
            // 最小值的下标
            int flg = i; // [O(n)]
            // 最大值的下标
            int maxFlg = i;// [O(n)]

            for(int j = i + 1; j < list.length - r; j++){ // [j = i + 1 O(n+1)] [list.length O(n^2)] [j++ O(n^2)]
                if(list[flg] > list[j]){  // O((n/4)^2)
                    flg = j;
                }else if(list[maxFlg] < list[j]){
                    maxFlg = j;
                }
            }

//            System.out.println("maxFlg=" + maxFlg);// 不计入算法时间
//            System.out.println("flg=" + flg);// 不计入算法时间


            SelectSort.swap(list, flg, i); // [O(n)]
//            if(maxFlg != i && flg != i) {
            if(maxFlg == i && flg != i){
                maxFlg = flg;
            }

            SelectSort.swap(list, list.length - 1 - r, maxFlg);

//            }


            r++;
        }

        long end  = System.currentTimeMillis();
        System.out.println("end自己排序:"+(end-start));

        for (int i:list){
//            System.out.print(i + "  ");
        }



//        System.out.println(SelectSort.check(list, cy));

        System.out.println("测试结果" + SelectSort.check(list, cy));
    }
    // 形成了一个功能体系所以拿出来
    public static void swap(int [] list, int flg, int i){
        if(flg != i){
            list[i] = list[i] ^ list[flg];
            list[flg] = list[i] ^ list[flg];
            list[i] = list[i] ^ list[flg];
        }
    }

    public static int [] ay(){
        int l = 100000;
        int [] ay = new int[l];
        Random r = new Random();

        for(int i = 0; i < l; i++){
            ay[i] = r.nextInt(l);
        }

        return ay;
    }

    public static boolean check(int [] source, int [] dist){
        boolean bl = true;

//        for(int i = 0; i < dist.length;i++){
//            System.out.print(dist[i]);
//        }
//        System.out.println("end source");

        System.out.println("系统排序-开始");
        long start = System.currentTimeMillis();
        Arrays.sort(dist);
        long end  = System.currentTimeMillis();
        System.out.println("系统排序-结束"+(end-start));

//        for(int i = 0; i < source.length;i++){
//            System.out.print(source[i]);
//        }
//        System.out.println("=====");
//        for(int i = 0; i < dist.length;i++){
//            System.out.print(dist[i]);
//        }
//        System.out.println("result");
        for(int i = 0; i < source.length; i++){
            if(source[i] != dist[i]){
                bl = false;
                break;
            }
        }

        return bl;
    }
}
